leetcode Container With Most Water

Posted on   |   In   |  

leetcode container with most water

Container With Most Water

link
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

题目大意:此题就是求出
$$max(min(a[i], a[j]) |i - j|)$$,其中0<=i, j<= n
分析:
对于任意的i,j; left = i, right = j;计算ij之间所组成的容器的最大值，首先计算以ij为索引的面积，min(a[i], a[j]) |i - j|,此时假设a[i] < a[j],这是后改变a[j]的值已经没有意义了，因为a[i]才是短板，此后计算的面积总是小于上面的面积，因此要改变短板，将短板变大，也就是说,找到大于短板的一个值

1
2
while(left < right && a[left] < a[i])
    left++;

同理，a[i] > a[j]也和上述分析一样
思路:用两个指针，left, right,left初值为0， right初值为n-1；比较两个索引处的值的大小:
(1) a[left] < a[right],求出此时的面积，此时a[left]为短板，要想使面积增大，则要扫描到一个大于a[left]的值，在扫描的过程中
(2)a[left] > a[right],求出此时的面积，此时a[right]为短板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        
        int maxA = 0;
        while(left < right){
            int area = min(height[left], height[right]) * (right - left);
            
            maxA = max(area, maxA);
                
            if(height[left] < height[right])
                left++;
            else
                right--;
        }
        
        return maxA;
    }
};

参考文章
http://bangbingsyb.blogspot.com/2014/11/leetcode-container-with-most-water.html